#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 * 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小 至少为 2 ，且
子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。



示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。
示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false
 *
 *
 * */

//todo 没思路 这玩意是前缀和
// 视频快结尾了我听出来了到底啥意思 这个是一个数学问题
// 首先你得需要想到前n项和  然后能想到这个数学问题就能做题了 考察离谱
// 假如如  a1+a2+...aj =n1 k(同乘以一个数) +q(表示余数) 式子2 a1+a2+...aj +...+an =n2 k +q(假设他俩余数相同)
// 则 式子2减去1得 aj+1 +'''+an=k(n2-n1) 则说明数组下标[j+1,n] 肯定可以整除k(这个k是题中的)
bool checkSubarraySum(vector<int> &nums, int k) {

    if (nums.size() <= 1)
        return false;

    unordered_map<int, int> mp;
    mp[0] = -1;//这个是干啥的
    int sum = 0;//sum 不重要 重要计算前的余数就行 余数+数能除尽就行
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
        sum = sum % k;
        if (mp.find(sum) != mp.end()) {
            int index = mp[sum];
            if (i - index >= 2)
                return true;
        } else {
            mp[sum] = i;//把余数和下标映射
        }


    }


    return false;


}